package com.xk._02算法篇._08dynamicProgramming;

/**
 * @description: 最长递增子序列
 * @author: xu
 * @date: 2022/10/19 8:26
 */
public class LIS {
    public static void main(String[] args) {
        int[] nums = { 10, 2, 2, 5, 1, 7, 101, 18 };
        System.out.println(new LIS().lengthOfLIS(nums));
        System.out.println(new LIS().lengthOfLIS1(nums));
        System.out.println(new LIS().lengthOfLIS2(nums));
    }

    // 动态规划
    // 时间：O(n^2), 空间：O(n)
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        // dp[i] 表示以 nums[i] 结尾的最长上升子序列的长度, i 属于 [0, nums.length)
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int max = 1;
        for (int i = 1; i < nums.length; i++) {
            dp[i] = 1;
            for (int j = i - 1; j >= 0; j--) {
                if (nums[i] <= nums[j]) continue;
                dp[i] = Math.max(dp[j] + 1, dp[i]);
            }
            max = Math.max(dp[i], max);
        }
        return max;
    }

    // 牌顶
    // 时间：O(n^2), 空间：O(n)
    public int lengthOfLIS1(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        // 牌顶数组
        int[] top = new int[nums.length];
        // 牌堆的数量
        int len = 0;
        // 遍历所有的牌
        for (int num : nums) {
            int j = 0;
            while (j < len) {
                // 找到一个 >= num 的牌顶
                if (top[j] >= num){
                    top[j] = num;
                    break;
                }
                j++; // 牌顶 < num
            }
            if (j == len) {
                top[j] = num;
                len++;
            }
        }
        return len;
    }

    // 牌顶 -- 二分搜索
    // 时间：O(nlogn), 空间：O(n)
    public int lengthOfLIS2(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        // 牌顶数组
        int[] top = new int[nums.length];
        // 牌堆的数量
        int len = 0;
        // 遍历所有的牌
        for (int num : nums) {
            int begin = 0;
            int end = len;
            while (begin < end) {
                int mid = (begin + end) >> 1;
                if (top[mid] >= num) {
                    end = mid;
                } else {
                    begin = mid + 1;
                }
            }
            // 覆盖牌顶
            top[begin] = num;
            // 检查是否要新建一个牌堆
            if (begin == len) len++;
        }
        return len;
    }
}
